import { BSTree,TreeNode } from "./00_二叉搜索树BSTree";
import { AVLTreeNode } from "./04_封装AVLTreeNode(左旋转操作)";
class AVLTree<T> extends BSTree<T> {
    // 重写调用createNode 方法
    protected createNode(value: T): TreeNode<T>{

        return new AVLTreeNode(value)
    }

    // 如何去找不平衡的节点
    checkBalance(node:AVLTreeNode<T>) {
        // 找到要找的节点的父节点
        let current = node.parent;
        // 当节点存在，去判断其是否平衡，不平衡的话则进行旋转操作
        while(current){
            if(!current.isBalanced){
                this.rebalance(current);
            }
            current = current.parent;
        }
    }

    //  如何找到不平衡的节点，先不管?

    // 假设已经找到了,那我们如何将这个节点变平衡
    // root 找到的不平衡的节点 根据不平衡的节点LL/RR/LR/RL让子树平衡
    rebalance(root: AVLTreeNode<T>){
        const pivot = root.higherChild;
        const current = pivot?.higherChild;
        let resultNode: AVLTreeNode<T> | null = null;

        if(pivot?.isLeft){ // L left
            if(current?.isLeft){ // LL left left
                resultNode = root.rightRotation()
            }else{ // LR left right
                pivot.leftRotation()
                // 左旋和右旋都将旋转后的根节点返回出去了，所以这里的resultNode是新的根节点
                resultNode = root.rightRotation()
            }
        }else{// R right
            if(current?.isLeft){ //RL right left
                pivot?.rightRotation();
          
                resultNode = root.leftRotation();
            }else{// RR right right
                resultNode = root.leftRotation();
            }
        }
        // 判断返回的pivot是否有父节点
        if(!resultNode?.parent){
            this.root = resultNode
        }
    }

}

const avlTree = new AVLTree<number>()

for( let i=0; i<20; i++ ){
    const randomNum = Math.floor(Math.random()*200)
    console.log(randomNum)
    avlTree.insert(randomNum)
}

// avlTree.insert(50)
// avlTree.insert(100)
// avlTree.insert(150)

avlTree.print()